{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mult(x, y):\n",
    "    nx, ny = len(x), len(y)\n",
    "\n",
    "    # auxiliary x\n",
    "    fx = np.zeros(nx + ny, dtype=np.float64)\n",
    "    fx[:nx] = list(map(int, reversed(x)))\n",
    "\n",
    "    # auxiliary y\n",
    "    fy = np.zeros(nx + ny, np.float64)\n",
    "    fy[:ny] += list(map(int, reversed(y)))\n",
    "\n",
    "    # convolution via FFT\n",
    "    fx = np.fft.fft(fx)\n",
    "    fy = np.fft.fft(fy)\n",
    "    z = np.fft.ifft(fx * fy).real.round().astype(int)\n",
    "\n",
    "    # carry over\n",
    "    for i in range(nx + ny - 1):\n",
    "        z[i + 1] += z[i] // 10\n",
    "        z[i] %= 10\n",
    "\n",
    "    return ''.join(map(str, reversed(z)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2092214183 * 2448001885 = 05121744263807734955\n",
      "7122461902 * 9593715983 = 68330876587525979666\n",
      "8617908461 * 3158102416 = 27216237531550941776\n",
      "3655867966 * 9064788350 = 33139669347334996100\n",
      "6622180692 * 4377254226 = 28986968419392604392\n",
      "6147274168 * 3384584963 = 20805971712451135784\n",
      "4714353304 * 5151447888 = 24285745371176621952\n",
      "9370611380 * 145283374 = 1361394037729196120\n",
      "2465911620 * 2801092645 = 06907246902002034900\n",
      "7836421288 * 8791219244 = 68891697631156866272\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    x, y = np.random.randint(1e+3, 1e+10, 2)\n",
    "    print(x, '*', y, '=', mult(str(x), str(y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
